The invention relates to a random number generator.
Random number generators (RNGs) are used for automatically generating random binary or multivalued numbers (random numbers). Random number generators are needed in many application fields, including for example: (i) cryptographic applications; (ii) stochastic simulations; (iii) testing of software and hardware; and (iv) computer games.
In what follows by way of example, cryptographic applications of random number generators will be considered. However, it is contemplated the system of the present invention of course is applicable to fields beyond cryptographic. Cryptographic applications include, for example;                For authentication:                    Challenge-response protocols            Zero-knowledge proofs                        For key sharing protocols:                    Diffie-Hellman methods                        For key generation:                    Session keys for symmetrical encryption methods            Key generation for asymmetric encryption methods (public-key methods)            Generation of binary noise (one-time pad, McEleice public-key method)            Parameter generation for public-key methods (e.g., generating random prime numbers)                        For other cryptographic applications:                    Password generation            Initial values (seeds) for deterministic random number generators (pseudorandom number generators)            Padding of cleartext blocks            Secure erasure of storage media (by multiple overwriting with random bit patterns).                        
In general there are two main kinds of generators, deterministic (i.e., pseudorandom number generators or PRNGs) and physical random number generators (i.e., true random number generators or TRNGs). Deterministic generators are algorithmic procedures that derive, from a randomly chosen initial value (IV), a much longer string of numbers that appears random. Naturally, this string per se cannot be truly random because of the deterministic character of the generating method.
In order that actually random strings of numbers can be generated, it is therefore necessary to employ a so-called physical random number generator. This uses either nondeterministic or chaotic physical processes to generate random numbers. The random numbers are generated by measuring and processing certain process measurements (e.g., thermal noise voltage across a resistance).
In what follows, it will be assumed that a cryptographic random number generator is implemented as a bit source. The individual bits are combined into blocks depending on the application (e.g., 56-bits for a key of the Data Encryption Standard or DES). It should be assumed in general that the bit strings generated by a cryptographic random number generator (e.g., a key) must remain secret in order not to compromise the security of the cryptosystem (in the list of applications in the preceding section, this does not hold for all the methods, up to challenge-response protocols and zero-knowledge proofs). In these cases, the random number generator generates the secret of the cryptographic method in question. With the aid of this secret, for example, cleartexts are encrypted. If the secret is unknown to the attacker, he always has to try out the choice of all possible bit strings (complete search). In the above example this would mean that the attacker, who has observed a cleartext encrypted with the unknown key, must try out a (statistical) average of 255 possible keys before he can expect to have found the key actually generated. This attack is the worst possible case from the viewpoint of the attacker. In order to attack a system with success, the attacker must be capable of predicting a certain number of bits that a generator generates at a certain point in time. This can happen without any knowledge of other bit strings generated by the generator or with a knowledge of bit strings that the generator has generated before or after the unknown bit string. The attacker can attempt to guess the generated bit string either in full or only in parts. In the latter case, he can find the remaining bits by a complete search.
In order to make such a prediction, the attacker has access to all known technical and scientific tools. He is limited only with respect to the costs to be incurred for the attack. It can be assumed that these have to fall below a defined cost limit (an economic argument: the expected gain by the attack should not exceed the costs of the attack).
The bit source can be subdivided into various security levels depending on the level of the cost limit. If a bit source resists all attacks for a given cost limit, then it should be regarded as a practically secure bit source in relation to this cost limit.
FIG. 14 depicts a model of a physical random number generator 1400 in the form of a physical bit source. A substantial component of the source is a dynamic, unpredictable physical system, so-called random source 1401. An internal (time-dependent) state can be associated with this random source 1401. At temporal intervals, the value of the state of random source 1401 is measured and processed (value acquisition 1402) and one or a plurality of random bits are generated herefrom (random bit generation 1403). Strings of random bits generated in this way are designated as internal random bits. These can next be subjected to algorithmic post-processing 1404. The mathematical post-processing 1404 is in general performed in order to improve the quality of the internal random numbers (a measure for the quality of random numbers must still be defined here-see the next section for more detail). In general, one speaks of random extraction 1405. This means the elimination of dependences between successively generated bits and the elimination of bias that is often present (unequal distribution of zeroes and ones). The random bits generated in this manner are output in a further step and, as appropriate, stored in an output memory (random bit output 1405).
As illustrated in FIG. 14, the physical random number generator 1400 is not an isolated system but is embedded in a physical environment 1406. It should be assumed that the measured state and thus also the random bits generated are dependent on certain physical quantities of the environment 1406. These include quantities such as for example the power supply voltage delivered to the device, the ambient temperature, or electromagnetic fields. Various kinds of generators can be distinguished on the basis of the nature of the physical system. Two essential kinds of physical systems are used: (i) quantum systems; and (ii) classical systems.
A quantum system means a system that is described by the laws of quantum mechanics. According to the current general scientific view, the phenomena occurring in such systems—on which random generation is then based—are truly random. Examples are decay processes in radioactive materials.
Classical physical systems, in contrast, are described by the deterministic laws of (classical) physics. There can be a variety of reasons why these systems can nevertheless be unpredictable. For systems with many degrees of freedom, the interactions that arise within the system are often too complex to be predicted with exactness. What is more, the initial state of the system can often not be determined exactly. This fact has further impacts in the case of so-called chaotic systems. In such systems, tiny changes in the initial state lead, in the course of time, to widely differing and unpredictable states of the system.
In order to assess a cryptographic bit source, it must be compared with the properties of the practically secure cryptographic bit source defined above. This includes a statistical assessment of the bit strings generated and a check of the possibilities of so-called side-channel attacks. These attacks actually take on great importance when random number generators are deployed in embedded systems. A side-channel attack is an attempt to predict the numbers generated by the generator or to influence their generation. This happens noninvasively by determining measured values from the environment of the generator (passive attacks) or by deliberately influencing the environment (active attacks). A further exacerbation of such an attack is represented by invasive side-channel attacks (for example, a hole might be drilled in the IC in order to measure signals there). Typical passive, noninvasive attacks are for example the measurement of the electromagnetic radiation from, or the power consumption of, the generator.
A variety of statistical tests are available for the statistical assessment of bit strings generated by a generator (e.g., Killmann, Wolfgang, and Werner Schindler, “A Proposal on Functionality Classes and Evaluation Methodology for Physical Random Number Generators” (Ein Vorschlag zu: Funktionalitätsklassen und Evaluationsmethodologie für physikalische Zufallszahlengeneratoren), Bundesamt für Sicherheit in der Informationstechnik (2001); Marsaglia, G., “Diehard: A Battery of Tests for Randomness,” URL http://stat.fsu.edu/pub/diehard/ (1996); Ruhkin, A. L., J. Sotot, J. Nechvatal, M. Smid, M. Levenson, D. Banks, M. Vangle, S. Leigh, S. Vo and J. Dray, “A Statistical Test Suite for the Validation of Cryptography Random Number Generators,” National Institute of Standards and Technology, Gaithersburg, Md. (2000); Schindler, Werner, “Evaluation Criteria for True (Physical) Random Number Generators Used in Cryptographic Applications,” in Kaliski, Burton S., Jr., etin Kaya Koç and Christof Paar (Eds.), “Cryptographic Hardware and Embedded Systems—CHES 2002, 4th International Workshop, Redwood Shores, Calif., U.S.A., Aug. 13-15, 2002, Revised Papers,” Lecture Notes in Computer Science, Vol. 2523, Springer (2003), ISBN 3-540-00409-2, pp. 1-2).
In principle, the problem of defining the concept of a random finite sequence arises in the assessment of these finite bit strings. According to Kolmogorov (Kolmogorov, Andrei N., “Three Approaches to the Quantitative Definition of Information,” in Problems in Information Transmission 1 (1965), No. 1), a finite sequence is random if it cannot be compressed. This means that the length of its shortest algorithmic description with reference to a selected computer model is of the same order of magnitude as the length of the sequence itself (this is the so-called Kolmogorov complexity of a sequence, with the Turing machine as the computer model). The basic idea here is that a sequence that is compressible must exhibit regularities in order to permit compression. Random sequences thus exhibit no regularities in this sense. Unfortunately, this concept does not lead to direct tests for the randomness of strings because the Kolmogorov complexity is not computable in the sense of computability theory.
The statistical tests are capable only of testing a bit string with respect to certain properties attributed to random (finite) bit strings. These properties are often derived from intuitive notions based on the general understanding of randomness. In fact, it can be shown of a number of tests that they are passed by bit strings random in the Kolmogorov sense (Li, Ming, and Paul Vitannyi, An Introduction to Kolmogorov Complexity and Its Applications, Springer-Verlag (1993), ISBN 0-387-94053-7).
Physical random number generators are known in a multiplicity of variants from the existing art. At the beginning of the development of random number generators, primarily external random number generators (i.e., those not embedded in ICs), were developed. A considerable selection of external random sources are available for this purpose. In present-day external random number generators, a multiplicity of random sources are used, for example radioactive sources, electronic thermal noise in resistances, or random events in the environment (e.g., time intervals between key presses on a keyboard).
It is only quite recently that random number generators have been embedded in commercial ICs. Here an important role is played by the kind of random source, its surface size on the IC, technical implementation and miniaturization. Up to now, however, hardly any note has been taken of the immunity of random number generators to side-channel attacks. Examples of implemented embedded random number generators are found in German Patent Application DE 101 17 362 A1; Cryptography Research, Inc., “Evaluation of the VIA C3 Nehemiah Random Number Generator,” URL http://www.cryptography.com/resources/whitepapers/VIA_rng.pdf; Cryptography Research, Inc., “The Intel Random Number Generator,” URL http://www.cryptography.com/resources/whitepapers/IntelRNG.pdf; U.S. patent application 20020186086; U.S. Pat. No. 4,855,690; German Patent DE 101 03 071 A1; Fischer, Viktor, and Milos Drutarovsky, “True Random Number Generator Embedded in Reconfigurable Hardware,” in Kaliski, Burton S., Jr., etin Kaya Koç and Christof Paar (Eds.), “Cryptographic Hardware and Embedded Systems—CHES 2002, 4th International Workshop, Redwood Shores, Calif., U.S.A., Aug. 13-15, 2002, Revised Papers,” Lecture Notes in Computer Science, Vol. 2523, Springer (2003), ISBN 3-540-00409-2, pp. 415-430, U.S. Pat. No. 5,706,218; International Patent Application WO 03/081417; German Patent Application DE 102 13 269 A1; U.S. patent application 20030185392; European Patent Application EP 1 343 073 A2; Tkacik, Thomas E., “A Hardware Random Number Generator”, in Kaliski, Burton S., Jr., etin Kaya Koç and Christof Paar (Eds.), “Cryptographic Hardware and Embedded Systems—CHES 2002, 4th International Workshop, Redwood Shores, Calif., U.S.A., Aug. 13-15, 2002, Revised Papers,” Lecture Notes in Computer Science, Vol. 2523, Springer (2003), ISBN 3-540-00409-2, pp. 450-453.
The invention begins from a so-called inverter chain random number generator as is disclosed in a wide variety of embodiments according to the existing art. By way of example, reference is made to German patent application DE 102 13 269 A1.
Referring to FIG. 15a, the fundamental component of these random number generators is a so-called ring oscillator 1508. It comprises the serial connection of an odd number K of inverters inv1, inv2, . . . , invK (logical NOT gates), the output of the last inverter invK being connected to the input of the first inverter inv1. As a result of the delay times of the individual inverters inv1, inv2, . . . , invK, a periodic oscillation comes about only when the number K of gates inv1, inv2, . . . , invK is odd.
In order to start and stop this oscillation, the first inverter inv1 can be replaced by a NAND gate nand1 with control input start/stop as shown in FIG. 15B. If this control input start/stop is set to a logical one (“1”), ring oscillator 1509 begins to oscillate.
FIG. 16A depicts a ring oscillator 1602 for K=3 having two inverters inv2, inv3 and one NAND gate nand1. FIG. 16B depicts an idealized signal trace at input 1611 and output 1612 of an inverter inv whose delay time is τ. If it is assumed that gates nand1, inv2, inv3 in the ring oscillator 1602 of FIG. 16A exhibit such an idealized behavior, then FIG. 16C depicts the idealized signal trace of the ring oscillator 1602 at points S, B, C and A=A′ after input S has been set to “1” for an elapsed time T.
For a technical implementation of the ring oscillator 1602 with K=3 using the CMOS component 74HCT04 (with no input NAND gate, FIG. 17A), FIG. 17B illustrates signal trace 1714 recorded with an oscilloscope at point A′ is illustrated in FIG. 17A. As is implied by the enlarged detail of the signal trace 1714 (in FIG. 17B), thermal motion of the electrons in the conductors of circuit 74HCT04 adds a thermal noise signal. FIG. 17C depicts an envelope 1715 of the noisy oscillation signal 1714 observed over a longer time interval t. As can be remarked, the noise in the flanks of the signal 1714 leads to the decision level being exceeded earlier or later than in the case of the noise-free signal. This temporally random shift in the flanks is called “jitter”. The difference between the maximum possible flank shift, observed with reference to a fixed time t1 (FIG. 17C), is identified by the reference character Δ. The magnitude of this difference Δ increases with the distance of the flank from the reference time t1. This phenomenon is known as “jitter accumulation.”
The oscillation signal 1714 of the ring oscillator 1702 from FIG. 17A, with a frequency f of approximately 25 MHz, averaged 512 times over a duration of 0.2 s, is illustrated in FIG. 18. Envelope 1802 of this averaged signal depicts the behavior of the autocorrelation for various temporal intervals from the trigger point. As can be seen from FIG. 18, the signal 1714 is not completely decorrelated by accumulated jitter until after approximately 0.28 s.
This indicates that the generated bits would be decorrelated, and thus may be used for a random bit source, only at a sampling rate ν of 3 Hz (or less). In order to increase the maximum possible rate νmax of generated random bits, a plurality of ring oscillators with various periods (i.e., with various values for K) can be combined. FIGS. 19A and 19B depict two embodiments of circuit arrangements based on a number L of ring oscillators 1901-1906. Here a parity check of the outputs (so-called XORing) is performed in each case. In concrete terms, this indicates that the outputs of the respective ring oscillators 1901-1906 are connected to the inputs of an XOR gate xor so that a “1” signal is generated at its output only if an odd number of logical “1” signals are present at the outputs of the ring oscillators 1901-1906. An even number of logical “1” values will generate a “0” signal at the output of the XOR gate. For this reason, the signal at the output of XOR gate xor is referred to as parity signal PS in what follows.
The two circuits of FIG. 19A and FIG. 19B differ solely in the configuration of the start/stop inputs of ring oscillators 1901-1906. In the first embodiment according to FIG. 19A, the start/stop inputs of the individual ring oscillators 1901-1903 are driven together. The second possibility, illustrated in FIG. 19B, is to drive the inputs separately to shift the initial phases of the individual oscillation signals relative to one another.
FIG. 20A illustrates a circuit 2002 with parity checking of two ring oscillators 2024, 2025 with a common start/stop signal. As can be seen in FIG. 20B and FIG. 20C, period P of parity signal PS 2029 remains constant. As a result of slow phase shifts of individual ring oscillator signals 2027, 2028, the signal trace 2029 of parity signal PS changes, within a period P over longer time intervals, as can be seen clearly in FIG. 21A. Over a time of approximately 0.2 s in FIG; 21B, envelope 2130 of parity signal PS, 2029 displays a more-variable autocorrelation that is smaller than the autocorrelation of the individual components (see FIG. 18). This parity checking of ring oscillators is used in many implementations of random number generators. The correlations cannot be completely removed with this technique, and so additional, rate-reducing, deterministic post-processing becomes unavoidable.
There is a need for a random number generator that does not require deterministic post-processing.